package advance.day01;

/**
 * 描述：
 *      找出一个字符串中最大的回文字符串的长度，时间复杂度O(n)
 *      R表示回文现在已有的回文字串的到达的最右的地方
 *      index表示R对应的回文子串的中心位置的索引
 *      进行扩展时有一下2种情况：
 *      1.R < i，暴力扩
 *      2.R > i，找到i位置已index为轴的对称点i'
 *          1)如果i'的回文串在index的回文串的之内，那么i位置的回文串半径等于i'
 *          2)如果i'的回文串超过了index回文串的范围，那么i位置的回文串的半径等于R - i
 *          3)如果i'的回文串边界与index回文串的边界重合，那么回文串的长度至少为R - i
 * @author hl
 * @version 1.0
 * @date 2020/11/4 11:12
 */
public class Manacher {
    public static char[] manacherString(String str){
        char[] chs = str.toCharArray();
        char[] res = new char[2 * chs.length + 1];
        int index = 0;
        for (int i = 0; i < res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : chs[index++];
        }
        return res;
    }
    public static int maxLcpsLength(String str){
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] chs = manacherString(str);
        int[] pArr = new int[chs.length];//记录每个位置的回文半径
        int r = -1;//记录目前回文串能达到的最右边
        int index = -1;//记录R对应的回文字符串的中心
        int max = 0; //记录最大的回文半径
        for (int i = 0; i < chs.length; i++) {
            pArr[i] = r > i ? Math.min(pArr[2 * index - i], r - i) : 1;
            while(i + pArr[i] < chs.length && i - pArr[i] > -1){
                if (chs[i + pArr[i]] == chs[i - pArr[i]]) {
                    pArr[i]++;
                }else{
                    break;
                }
            }
            if (i + pArr[i] > r) {
                r = i + pArr[i];
                index = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max;//pArr[i]++;记录的都是最长回文半径+1的值，返回值应该减1
    }
    public static void main(String[] args) {
        String str1 = "abc1234321ab";
        System.out.println(maxLcpsLength(str1));


    }

}
